package 每日一题;

/**
 * 79. 单词搜索
 * 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
 *
 * 单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
 * 输出：true
 * 示例 2：
 *
 *
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
 * 输出：true
 * 示例 3：
 *
 *
 * 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
 * 输出：false
 *
 *
 * 提示：
 *
 * m == board.length
 * n = board[i].length
 * 1 <= m, n <= 6
 * 1 <= word.length <= 15
 * board 和 word 仅由大小写英文字母组成
 *
 *
 */
public class D220701_T0079 {
    //深度递归 回溯

    public static boolean exist(char[][] board, String word) {

        char[] words = word.toCharArray();

        for (int x = 0; x < board.length; x++) {
            for (int y = 0; y < board[x].length; y++) {
                if (board[x][y] == words[0]) {
                    boolean dfs = dfs(board, words, x, y, 0);
                    if (dfs) {
                        return true;
                    }
                }

            }
        }

        return false;

    }


    /**
     * 是否存从索引开始的单词子串
     *
     * @param board 二维网格
     * @param words 要搜索的单词
     * @param x     当前的横坐标
     * @param y     当前的纵坐标
     * @param index 当前单词的字符索引位置
     * @return
     */
    public static boolean dfs(char[][] board, char[] words, int x, int y, int index) {

        if (index >= words.length) {  //必须先判断 字符坐标 是否越界 ，如果越界说明已经搜索完毕了 此时返回true
            return true;
        }
        //判断 坐标是否越界  坐标字符 与索引字符是否一致
        if (x >= board.length || x < 0 || y >= board[x].length || y < 0 || words[index] != board[x][y]) {
            return false;
        }

        char targetChar = board[x][y];
        //当前网格坐标字符与 单词索引坐标字符一致 将当前字符置为 $ 防止在本次搜索中 被重复搜索
        board[x][y] = '$';

        //继续向上下左右 搜索后面的子串
        boolean upResult = dfs(board, words, x - 1, y, index + 1);
        boolean downResult = dfs(board, words, x + 1, y, index + 1);
        boolean leftResult = dfs(board, words, x, y - 1, index + 1);
        boolean rightResult = dfs(board, words, x, y + 1, index + 1);

        //回溯
        board[x][y] = targetChar;
        //返回从此坐标开始 搜索 index坐标开始的word子串 的结果
        return upResult || downResult || leftResult || rightResult;

    }

    public static void main(String[] args) {

        boolean exist = D220701_T0079.exist(new char[][]{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED");
        System.out.println(exist);

    }

}
